public class MySingleList {
    static class ListNode {
        public int val;
        public ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }
    public ListNode head;

    public void createNode() {
        ListNode Node1 =new ListNode(11);
        ListNode Node2 =new ListNode(22);
        ListNode Node3 =new ListNode(33);
        ListNode Node4 =new ListNode(44);
        ListNode Node5 =new ListNode(55);

        Node1.next = Node2;
        Node2.next = Node3;
        Node3.next = Node4;
        Node4.next = Node5;

        this.head = Node1;
    }
    //打印链表
    public void show() {
        ListNode tmp = head;
        while(tmp != null) {
            System.out.print(tmp.val+" ");
            tmp = tmp.next;
        }
        System.out.println();
    }
    //打印指定链表
    public void show(ListNode listNode) {
        ListNode tmp = listNode;
        while(tmp != null) {
            System.out.print(tmp.val+" ");
            tmp = tmp.next;
        }
        System.out.println();
    }
    //求链表长度
    public int size() {
        ListNode tmp = head;
        int count = 0;
        while(tmp != null) {
            count++;
            tmp = tmp.next;
        }
        return count;
    }
    public int size(ListNode listNode) {
        ListNode tmp = listNode;
        int count = 0;
        while(tmp != null) {
            count++;
            tmp = tmp.next;
        }
        return count;
    }
    //是否含有某个数据key
    public Boolean contains(int key) {
        ListNode tmp = head;
        while(tmp != null) {
            if(tmp.val == key) {
                return true;
            }
            tmp = tmp.next;
        }
        return false;
    }
    //头插
    public void addFirst(int date) {
        ListNode tmp = head;
        ListNode head1 = new ListNode(date);
        head1.next = tmp;
        head = head1;
    }
    //尾插
    public void addLast(int date) {
        ListNode head1 = new ListNode(date);
        if(head == null) {
            head = head1;
            return;
        }
        ListNode tmp = head;
        while(tmp.next != null) {
            tmp = tmp.next;
        }
        tmp.next = head1;
    }
    //从指定位置插入元素
    public void addIndex(int index,int val) {
        if(index < 0  ||index > size()) {
            return;
        }
        if(index == 0) {
            addFirst(val);
            return;
        }
        if(index == size()) {
            addLast(val);
            return;
        }
        ListNode tmp = findIndex(index);
        ListNode head2 = new ListNode(val);
        head2.next = tmp.next;
        tmp.next = head2;
    }
    //获取某下标元素的前一个元素
    private ListNode findIndex(int index) {
        ListNode tmp = head;
        int count = 0;
        while(count != index-1) {
            count++;
            tmp = tmp.next;
        }
        return tmp;
    }
    //删除指定元素key
    public void remove(int key) {
        if(head == null) return;
        //第一个数据就找到key
        if(head.val == key) {
            head =  head.next;
            return;
        }
        ListNode tmp = findRemove(key);
        //没找到key
        if(tmp == null) {
            System.out.println("未找到key");
            return;
        }
        //使key的前一个元素指向key的下一个元素
        tmp.next = tmp.next.next;
    }
    //找到要删除元素key的前一个元素
    public ListNode findRemove(int key) {
        ListNode tmp = head;
        while(tmp.next != null) {
            if(tmp.next.val == key) {
                return tmp;
            }
            tmp = tmp.next;
        }
        return null;
    }
    //删除全部key
    public void removeAll(int key) {
        if(head == null) return;
        //第一个数据就找到key
        while(head.val == key) {
            head =  head.next;
        }
        ListNode cur = head.next;
        ListNode prev = head;
        while(cur != null) {
            if(cur.val == key) {
                prev.next = cur.next;
                cur = cur.next;
            }else {
                prev = cur;
                cur = cur.next;
            }
        }
    }
    //清除所有数据
    public void clear() {
        ListNode cur = head;
        while(cur != null) {
            ListNode curN = cur.next;
            cur.next = null;
            cur = curN;
        }
        head = null;
    }
    //反转链表 迭代法
    public ListNode reverseList() {
        if(head == null ||head.next == null) {
            return head;
        }
        ListNode cur = head.next;
        head.next = null;
        while(cur != null) {
            ListNode curN = cur.next;
            //头插
            cur.next = head;
            head = cur;

            cur = curN;
        }
        return head;
    }
    //找到链表的中间节点 循环2遍
    public ListNode findMiddleNode() {
        if(head == null) {
            return null;
        }
        int len = size();
        ListNode tmp = head;
        for (int i = 0; i < len/2; i++) {
            tmp = tmp.next;
        }
        return tmp;
    }
    //找到链表中间 循环一遍
    public ListNode findMiddleNode1() {
        if(head == null) {
            return null;
        }
        ListNode tmp1 = head;
        ListNode tmp2 = head;
//        if(tmp1 == null || tmp1.next == null) {
//            tmp1 = tmp1.next.next;
//            tmp2 = tmp2.next;
//        }
        while(tmp1 != null && tmp1.next != null) {
            tmp1 = tmp1.next.next;
            tmp2 = tmp2.next;
        }
        return tmp2;
    }
    //找到倒数第K个节点 循环2遍
    public ListNode findKLast(int k) {
        int len = size();
        if(k <= 0 || k > len) {
            return null;
        }
        ListNode tmp = head;
        for (int i = 0; i < len-k; i++) {
            tmp = tmp.next;
        }
        return tmp;
    }
    //找到倒数第K个节点 循环1遍
    public ListNode findKLast1(int k) {
        if(k <= 0) return null;
        ListNode cur = head;
        ListNode curN = head;
        for (int i = 0; i < k-1; i++) {
            if(cur != null && cur.next != null) {
                //k>size() 置为null
                cur = cur.next;
            }else{
                return null;
            }
        }
        while(cur.next != null) {
            cur = cur.next;
            curN = curN.next;
        }
        return curN;
    }
    //给定一个x 大于x的在前面 其他的在后面
    public ListNode partition(int x) {
        ListNode q1 = null;
        ListNode q2 = null;
        ListNode h1 = null;
        ListNode h2 = null;
        ListNode cur = head;

        while(cur != null) {
            if(cur.val < x) {//小于x
                if(q2 == null) {
                    q2 = cur;
                    q1 = cur;
                }else {
                    q2.next = cur;
                    q2 = q2.next;
                }
                cur = cur.next;
            }else {//大于x
                if(h2 == null) {
                    h2 = cur;
                    h1 = cur;
                }else {
                    h2.next = cur;
                    h2 = h2.next;
                }
                cur = cur.next;
            }
        }
        if(q2 != null) {
            q2.next = h1;
        }else {
            q1 = h1;
        }
        if(h2 != null) {
            h2.next = null;
        }
        return q1;
    }
    //回文链表
    public Boolean chkPalindrome() {
        //1.找到中间节点
        if(head == null) {
            return false;
        }
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        //2.反转中间节点后链表
        ListNode cur = slow.next;
        while(cur != null) {
            ListNode curN = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curN;
        }
        //3.判断slow与head后走是否相遇
        ListNode tmp = head;
        while(slow != tmp) {
            if(slow.val == tmp.val) {
                if(tmp.next ==  slow) {
                    return true;
                }
                slow = slow.next;
                tmp = tmp.next;
            }else {
                return false;
            }
        }
        return true;
    }
    //寻找两个链表的相同节点
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == null || headB == null) {
            return null;
        }
        int A = size(headA);
        int B = size(headB);
        if(A > B) {
            for (int i = 0; i < A-B; i++) {
                headA = headA.next;
            }
        }else {
            for (int i = 0; i < B-A; i++) {
                headB = headB.next;
            }
        }
        while(headA != headB) {
            if(headA.next == null || headB.next == null) {
                return null;
            }
            headA = headA.next;
            headB = headB.next;
        }
        return headA;
    }
    //判断链表内是否有环
    public boolean hasCycle(ListNode head) {
        if(head == null) {
            return false;
        }
        ListNode fast = head.next;
        ListNode slow = head;
        while(fast != slow) {
            if(fast == null || fast.next == null) {
                return false;
            }
            fast = fast.next.next;
            slow = slow.next;
        }
        return true;
    }
}
